//https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/
package codeRandomThoughts.Test28找出字符串中第一个匹配项的下标;

import java.util.Arrays;

/**
 * 第一次自己写KMP 跳完绳回来再写一遍
 */
public class Solution2 {
    public static int strStr(String haystack, String needle) {
        int[] next = getNextFromPattern(needle);
        //用双指针扫描主串和子串
        int i = 0;
        int j = 0;
        char[] str = haystack.toCharArray();
        char[] pattern = needle.toCharArray();
        for (i = -1; i < str.length - 1; i++) {


            while (j > 0 && str[i + 1] != pattern[j]) {
                j = next[j];
            }
            if (str[i + 1] == pattern[j]) {
                j++;
            }

            if (j >= pattern.length) {
                return i - j + 2;
            }
        }

        return -1;
    }

    public static int[] getNextFromPattern(String needle) {
        char[] chars = needle.toCharArray();
        int[] next = new int[needle.length() + 1];//让next数组下标从1开始 有必要吗?
        next[1] = 0;

        for (int i = 2; i <= needle.length(); i++) {
            //比较前缀的后面和后缀的后面是否相同
            if (chars[next[i - 1]] == chars[i - 1]) {
                //如果相同,next数组的值等于前一项加1
                next[i] = next[i - 1] + 1;
            } else {
                //如果不同
                //根据之前的next数组进行回退比较
                int jumpTo = next[i - 1];
                while (chars[next[jumpTo]] != chars[i - 1] && jumpTo > 1) {
                    jumpTo = next[jumpTo];
                }
                if (chars[next[jumpTo]] == chars[i - 1]) {
                    next[i] = next[jumpTo] + 1;
                } else {
                    next[i] = 0;
                }
            }
        }

        return next;
    }


    public static void main(String[] args) {
        String str = "aadascvdsv";
        String p = "vds";
        System.out.println(strStr(str, p));
    }
}
